package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1590 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 看了一眼，是我做不出来的题
     * @return:
     */
    class Solution {
        public int minSubarray(int[] nums, int p) {
            int N = nums.length;
            //记录位置为i时，由0->i的前缀和对p的余数
            int[] prefixSum = new int[N];
            int sum = 0;
            for (int i = 0; i < N; i++) {
                sum += nums[i] % p;
                sum %= p;
                prefixSum[i] = sum;
            }
            //整个数组的余数为sum (当然也等于prefixSum[N-1])
            //余数为0 不必移除 整个串满足
            if (sum == 0) {
                return 0;
            }
            //最终结果不超过N 定义N作为边界值
            int ans = N;
            //这个map的key和value  表示索引值为value的位置，期望遇到前缀和对p取余的余数为key
            //有点像两数之和 每个位置将自己的期望值记录在map中，并判断自己这个位置处的余数是否满足了其它位置的要求
            Map<Integer, Integer> record = new HashMap<>();
            //在遍历之前，因为已经知道了整个串的余数为sum,那么先提一次要求吧！
            record.put(sum, -1);
            for (int i = 0; i < N; i++) {
                //位置i处的余数
                int cur = prefixSum[i];
                //该位置处 期望的余数
                int target = (cur + sum) % p;
                //1.记录自己的要求 将当前位置的期望值和位置存入
                record.put(target, i);
                //2.判断是否符合别人的要求
                if (record.containsKey(cur)) {
                    int size = i - record.get(cur);
                    ans = Math.min(ans, size);
                    record.remove(cur);
                }
            }
            if (ans != N) {
                return ans;
            }
            return -1;
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1590 an = new LC1590();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
